package backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : Rookie
 * @description : 分割回文子串
 * @date : 2023/11/26
 */
public class DivPalindromeSubStr {

    public static void main(String[] args) {
        String str = "aab";
        List<List<String>> result = new ArrayList<>();
        backtrack(str,0,new ArrayList<>(),result);
        System.out.println(result);
    }

    private static void backtrack(String str,int startIndex,List<String> path,List<List<String>> result) {
        if (startIndex == str.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < str.length(); i++) {
            String substr = str.substring(startIndex, i + 1);
            if (isPalindromeStr(substr)) {
                path.add(substr);
                backtrack(str,i+1,path,result);
                path.remove(path.size()-1);
            }
        }
    }

    /**
     * 判断字符串是否是回文子串
     * @param str
     * @return
     */
    private static boolean isPalindromeStr(String str) {
        int start=0,end=str.length()-1;
        while (start<end) {
            if (str.charAt(start) != str.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
}
